package com.leetcode.alibaba;

/**
 * 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 */
public class 判断是不是平衡二叉树 {
	boolean isBalanced = true; // 默认标记为true

	public boolean IsBalanced_Solution(TreeNode root) {
		TreeDepth(root);
		return isBalanced;
	}

	public int TreeDepth(TreeNode root) {
		if (root == null)
			return 0; // 递归终止
		int l = TreeDepth(root.left);
		int r = TreeDepth(root.right);

		if (Math.abs(l - r) > 1) {
			isBalanced = false;  // 不是平衡树
		}

		return Math.max(l, r) + 1; // 求深度
	}

	public int TreeDepth1(TreeNode root) {
		if (root == null)
			return 0;
		int l = TreeDepth(root.left);
		if (l == -1) return -1;  // 提前返回
		int r = TreeDepth(root.right);
		if (r == -1) return -1;  // 提前返回
		if (Math.abs(l - r) > 1) {
			isBalanced = false;  // 不是平衡树
			return -1;  // 加一个标记-1，已经不可能是平衡树了
		}

		return Math.max(l, r) + 1;
	}
}
